翻訳と辞書 Words near each other ・ Polynomial least squares ・ Polynomial lemniscate ・ Polynomial long division ・ Polynomial matrix ・ Polynomial regression ・ Polynomial remainder theorem ・ Polynomial representations of cyclic redundancy checks ・ Polynomial ring ・ Polynomial sequence ・ Polynomial signal processing ・ Polynomial SOS ・ Polynomial texture mapping ・ Polynomial transformations ・ Polynomial Wigner–Ville distribution ・ Polynomial-time algorithm for approximating the volume of convex bodies ・ Polynomial-time approximation scheme ・ Polynomial-time reduction ・ Polynomially reflexive space ・ Polynomiography ・ Polynoncus ・ Polynormal subgroup ・ Polynormande ・ Polynove Pole ・ Polynoxylin ・ Polynuclear ・ Polynucleobacter ・ Polynucleobacter acidiphobus ・ Polynucleobacter cosmopolitanus ・ Polynucleobacter difficilis ・ Polynucleobacter necessarius Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Polynomial-time approximation scheme ： ウィキペディア英語版 Polynomial-time approximation scheme In computer science, a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems). A PTAS is an algorithm which takes an instance of an optimization problem and a parameter ε > 0 and, in polynomial time, produces a solution that is within a factor 1 + ε of being optimal (or 1 - ε for maximization problems). For example, for the Euclidean traveling salesman problem, a PTAS would produce a tour with length at most (1 + ε)''L'', with ''L'' being the length of the shortest tour.〔Sanjeev Arora, Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM 45(5) 753–782, 1998.〕 The running time of a PTAS is required to be polynomial in ''n'' for every fixed ε but can be different for different ε. Thus an algorithm running in time ''O''(''n''1/ε) or even ''O''(''n''exp(1/ε)) counts as a PTAS. ==Variants== 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Polynomial-time approximation scheme」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.